home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / tcisam.zip / INXRTNS.C < prev    next >
Text File  |  1987-08-21  |  11KB  |  305 lines
  1. /*
  2.  * INXRTNS.C - index file support routines
  3.  *
  4.  *                      Copyright (c) 1987, Jim Mischel
  5.  * Modifications:
  6.  *
  7.  * 08/13/87 - jim - original coding
  8.  * 08/21/87 - jim - flush the buffer after every write (iwrite_dat and iwrite_inx)
  9.  */
  10.  
  11. #include "inxdefs.h"
  12.  
  13.  
  14. /************************************************************************/
  15. /*                                                                      */
  16. /*                       Internal support routines                      */
  17. /*                                                                      */
  18. /************************************************************************/
  19.  
  20. /*
  21.  * iget_next() - read the next index record in sequence.
  22.  * If successful, '*irec' contains the next index record and the function
  23.  * returns 0.
  24.  * If unsuccessful, '*irec' is undefined and the function returns EOF.
  25.  */
  26. int iget_next(df_rec *db_control, inx_rec *irec)
  27. {
  28.   /* see if we've already reached the end of the file */
  29.   if (irec->if_flags & ETHRD) {
  30.     db_control->df_flags |= DF_EOF;
  31.     return(EOF);
  32.   }
  33.  
  34.   if (irec->if_flags & RTHRD) {         /* Right node is a thread pointer */
  35.     if (iread_inx(db_control,irec->if_right_node))
  36.       return(EOF);
  37.   }
  38.   else {                                /* Right node is a tree pointer */
  39.  
  40.   /*
  41.    * Read the right node, then follow the left nodes until we come to a leaf.
  42.    * We'll know a leaf when the left node pointer is a thread pointer.
  43.    */
  44.     if (iread_inx(db_control,irec->if_right_node))
  45.       return(EOF);
  46.     while (!(db_control->df_inx_buff.if_flags & LTHRD))
  47.       if (iread_inx(db_control,db_control->df_inx_buff.if_left_node))
  48.         return(EOF);
  49.   } /* else */
  50.  
  51.   return(0);
  52. } /* iget_next */
  53.  
  54. /*
  55.  * iget_prev() - read the previous index record in sequence.
  56.  * If successful, '*irec' contains the previous index   record and the function
  57.  * returns 0.
  58.  * If unsuccessful, '*irec' is undefined and the function returns EOF.
  59.  */
  60. int iget_prev(df_rec *db_control, inx_rec *irec)
  61. {
  62.   if (irec->if_flags & BTHRD) {
  63.     db_control->df_flags |= DF_TOF;
  64.     return(EOF);
  65.   }
  66.  
  67.   if (irec->if_flags & LTHRD) {         /* Left node is a thread pointer */
  68.     if (iread_inx(db_control,irec->if_left_node))
  69.       return(EOF);
  70.   }
  71.   else {                                /* Left node is a tree pointer */
  72.  
  73.   /*
  74.    * Read the left node, then follow the right nodes until we come to a leaf.
  75.    * We'll know a leaf when the right node pointer is a thread pointer.
  76.    */
  77.     if (iread_inx(db_control,irec->if_left_node))
  78.       return(EOF);
  79.     while (!(db_control->df_inx_buff.if_flags & RTHRD))
  80.       if (iread_inx(db_control,db_control->df_inx_buff.if_right_node))
  81.         return(EOF);
  82.   } /* else */
  83.  
  84.   return(0);
  85. } /* iget_prev */
  86.  
  87. /*
  88.  * isearch() - searches for key value '*key'    in data file using a simple
  89.  * binary tree search.
  90.  * The function returns:
  91.  *   -1 : The specified key was not found.  '*db_control->df_inx_buff'
  92.  *        would be the parent if '*key' was added to    the file.
  93.  *        '*db_control->df_dat_buff' contains the data record last read.
  94.  *    0 : The specified key was found.  '*db_control->df_inx_buff' contains
  95.  *        the index record and '*db_control->df_dat_buff' contains the
  96.  *        data record.
  97.  *    1 : The specified key was not found.  '*db_control->df_inx_buff'
  98.  *        would be the parent if '*key' was added to    the file.
  99.  *        '*db_control->df_dat_buff' contains the data record last read.
  100.  *    2 : An error was encountered reading either the index or the data file.
  101.  *        '*db_control->df_inx_buff' and '*db_control->df_dat_buff' are
  102.  *        undefined.
  103.  */
  104. int isearch(df_rec *db_control, char *key)
  105. {
  106.   if (iget_root(db_control))
  107.     return(ierrno);
  108.  
  109.   /* Binary tree search */
  110.   while (1) {
  111.  
  112.     /* read the data record */
  113.     if (iread_dat(db_control,db_control->df_inx_buff.if_dat_ptr))
  114.       return(2);                        /* data file read error */
  115.  
  116.     switch ((*db_control->df_cmp)(key,db_control->df_key_ptr)) {
  117.       case -1        :                  /* key is less than data record key */
  118.         if (db_control->df_inx_buff.if_flags & LTHRD)
  119.           return(-1);                   /* thread pointer (not found) */
  120.         if (iread_inx(db_control,db_control->df_inx_buff.if_left_node))
  121.           return(2);                    /* index file read error */
  122.         break;
  123.       case 0    :
  124.         return(0);      /* found */
  125.       case 1    :                       /* key is greater than data record key */
  126.         if (db_control->df_inx_buff.if_flags & RTHRD)
  127.           return(1);                    /* right thread (not found) */
  128.         if (iread_inx(db_control,db_control->df_inx_buff.if_right_node))
  129.           return(2);                    /* inx file read error */
  130.         break;
  131.       default   :
  132.         puts("invalid return value from comparison routine");
  133.         return(2);
  134.     } /* switch */
  135.   } /* while */
  136. } /* isearch */
  137.  
  138. /*
  139.  * iget_root() - reads the root of the binary tree into the index buffer.
  140.  * Returns 0 if successful, error status if unsuccessful.  If the file
  141.  * is empty, EOF is returned.  If unsuccessful, the contents of the index
  142.  * buffer is undefined.
  143.  */
  144. int iget_root(df_rec *db_control)
  145. {
  146.   if (iread_inx(db_control,0L))
  147.     return(ierrno);
  148.   if (db_control->df_inx_buff.if_left_node == 0L)
  149.     return(ierror(EOF));                /* empty file */
  150.   if (iread_inx(db_control,db_control->df_inx_buff.if_left_node))
  151.     return(ierrno);
  152.   return(0);
  153. } /* iget_root */
  154.  
  155.  
  156. /************************************************************************/
  157. /*                                                                      */
  158. /*                      File I/O primitives                             */
  159. /*                                                                      */
  160. /*  These are the only routines that actually access the files.         */
  161. /*                                                                      */
  162. /************************************************************************/
  163.  
  164. /*
  165.  * iread_inx() - reads the index record at seek_pos into the index buffer.
  166.  * Returns 0 if successful, I_INXRD if unsuccessful.  If unsuccessful,
  167.  * the contents of the index buffer is undefined.
  168.  */
  169. int iread_inx(df_rec *db_control, long seek_pos)
  170. {
  171.   if (fseek(db_control->df_inx_file,seek_pos,SEEK_SET))
  172.     return(ierror(I_INXRD));
  173.   db_control->df_inx_ptr = seek_pos;
  174.   if (fread(&db_control->df_inx_buff,sizeof(inx_rec),1,
  175.             db_control->df_inx_file) != 1)
  176.     return(ierror(I_INXRD));
  177.   return(ierror(0));
  178. } /* iread_inx */
  179.  
  180. /*
  181.  * iwrite_inx() - write the record from 'irec' to the index file at position
  182.  * 'seek_pos'.  Returns 0 if successful,        I_INXWT if unsuccessful.
  183.  */
  184. int iwrite_inx(df_rec *db_control, inx_rec *irec, long seek_pos)
  185. {
  186.   if (fseek(db_control->df_inx_file,seek_pos,SEEK_SET))
  187.     return(ierror(I_INXWT));
  188.   db_control->df_inx_ptr = seek_pos;
  189.   if (fwrite(irec,sizeof(inx_rec),1,db_control->df_inx_file) != 1)
  190.     return(ierror(I_INXWT));
  191.   if (fflush(db_control->df_inx_file))
  192.     return(ierror(I_INXWT));
  193.   return(ierror(0));
  194. } /* iwrite_inx */
  195.  
  196. /*
  197.  * iread_dat() - reads the data record at seek_pos into the data buffer.
  198.  * Returns 0 if successful, I_DATRD if unsuccessful.  If unsuccessful,
  199.  * the contents of the data buffer is undefined.
  200.  */
  201. int iread_dat(df_rec *db_control, long seek_pos)
  202. {
  203.   if (fseek(db_control->df_dat_file,seek_pos,SEEK_SET))
  204.     return(ierror(I_DATRD));
  205.   db_control->df_dat_ptr = seek_pos;
  206.   if (fread(db_control->df_dat_buff,db_control->df_rec_size,1,
  207.             db_control->df_dat_file) != 1)
  208.     return(ierror(I_DATRD));
  209.   return(ierror(0));
  210. } /* iread_dat */
  211.  
  212. /*
  213.  * iwrite_dat() - write the record from 'datrec' to the data file at position
  214.  * 'seek_pos'.  Returns 0 if successful,        I_DATWT if unsuccessful.
  215.  */
  216. int iwrite_dat(df_rec *db_control, void *datrec, long seek_pos)
  217. {
  218.   if (fseek(db_control->df_dat_file,seek_pos,SEEK_SET))
  219.     return(ierror(I_DATWT));
  220.   db_control->df_dat_ptr = seek_pos;
  221.   if (fwrite(datrec,db_control->df_rec_size,1,db_control->df_dat_file) != 1)
  222.     return(ierror(I_DATWT));
  223.   if (fflush(db_control->df_dat_file))
  224.     return(ierror(I_DATWT));
  225.   return(ierror(0));
  226. } /* iwrite_dat */
  227.  
  228. /*
  229.  * ierror() - set the global variable 'ierrno'  to the value supplied in 'e'
  230.  * and return the error number.
  231.  */
  232. int ierror(int e)
  233. {
  234.   ierrno = e;
  235.   return(ierrno);
  236. }
  237.  
  238. /************************************************************************/
  239. /*                                                                      */
  240. /*                        Comparison routines                           */
  241. /*                                                                      */
  242. /*  These routines all return -1 if *arg1 < *arg2                       */
  243. /*                             0 if *arg1 == *arg2                      */
  244. /*                             1 if *arg1 > *arg2                       */
  245. /************************************************************************/
  246.  
  247. int icmp_uchar(void *arg1, void *arg2)
  248. {
  249.   return ((*(unsigned char *)arg1 < *(unsigned char *)arg2) ? -1 :
  250.           (*(unsigned char *)arg1 > *(unsigned char *)arg2) ? 1 : 0);
  251. }
  252.  
  253. int icmp_schar(void *arg1, void *arg2)
  254. {
  255.   return ((*(signed char *)arg1 < *(signed char *)arg2) ? -1 :
  256.           (*(signed char *)arg1 > *(signed char *)arg2) ? 1 : 0);
  257. }
  258.  
  259. int icmp_uint(void *arg1, void *arg2)
  260. {
  261.   return ((*(unsigned int *)arg1 < *(unsigned int *)arg2) ? -1 :
  262.           (*(unsigned int *)arg1 > *(unsigned int *)arg2) ? 1 : 0);
  263. }
  264.  
  265. int icmp_sint(void *arg1, void *arg2)
  266. {
  267.   return ((*(signed int *)arg1 < *(signed int *)arg2) ? -1 :
  268.           (*(signed int *)arg1 > *(signed int *)arg2) ? 1 : 0);
  269. }
  270.  
  271. int icmp_ulong(void *arg1, void *arg2)
  272. {
  273.   return ((*(unsigned long *)arg1 < *(unsigned long *)arg2) ? -1 :
  274.           (*(unsigned long *)arg1 > *(unsigned long *)arg2) ? 1 : 0);
  275. }
  276.  
  277. int icmp_slong(void *arg1, void *arg2)
  278. {
  279.   return ((*(signed long *)arg1 < *(signed long *)arg2) ? -1 :
  280.           (*(signed long *)arg1 > *(signed long *)arg2) ? 1 : 0);
  281. }
  282.  
  283. int icmp_string(void *arg1, void *arg2)
  284. {
  285.   int r;
  286.  
  287.   return(((r = strcmp((char *)arg1, (char *)arg2)) == 0) ? 0 :
  288.          (r > 0) ? 1 : -1);
  289. }
  290.  
  291. #ifdef FLOAT_KEY
  292.  
  293. int icmp_float(void *arg1, void *arg2)
  294. {
  295.   return ((*(float *)arg1 < *(float *)arg2) ? -1 :
  296.           (*(float *)arg1 > *(float *)arg2) ? 1 : 0);
  297. }
  298.  
  299. int icmp_double(void *arg1, void *arg2)
  300. {
  301.   return ((*(double *)arg1 < *(double *)arg2) ? -1 :
  302.           (*(double *)arg1 > *(double *)arg2) ? 1 : 0);
  303. }
  304. #endif
  305.